package com.algorithm.dp;

import io.netty.util.internal.MathUtil;

public class Test {
    public static void main(String[] args) {
        //q();
        //w();
        e();
    }

    /**
     * 下降求最小和
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

     示例:

     输入: [-2,1,-3,4,-1,2,1,-5,4],
     输出: 6
     解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     进阶:

     如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
     状态转移方程为 : f[i] = max{f[i-1] + v[i],v[i]}
     */
    public static final void q(){
        int[] arr =  {-2,1,-3,4,-1,2,1,-5,4};
        int[] dp = new int[arr.length];
        dp[0] = Math.max(0,arr[0]);
        int temp = dp[0];
        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i],arr[i]);
            if (dp[i] > temp) temp = dp[i];
        }
        System.out.println(temp);
    }

    /**
     * 给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。

     下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
     */
    // 状态转移方程: f[i][j] = min{f[i-1][j-1],f[i-1][j],f[i-1][j+1]}+v[i][j]
    public static final void w(){
        int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
        int height = arr.length;
        int oldWidth = arr[0].length;
        int[][] dp = new int[height][oldWidth +2];

        for (int i = 0; i < height; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][dp[0].length -1] = Integer.MAX_VALUE;
        }
        dp[0][0] = Integer.MAX_VALUE;
        for (int i = 1; i < oldWidth+1; i++) {
            dp[0][i] = arr[0][i-1];
        }
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < dp[i].length -1; j++) {
                //dp[i][j] = getMin(arr,i-1,j) + arr[i][j];
                dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]) + arr[i][j-1];
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dp[0].length; i++) {
            if (dp[height -1][i] < min){
                min = dp[height -1][i];
            }
        }
        System.out.println(min);
    }

    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

     机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

     问总共有多少条不同的路径？
     */
    public static final void e(){
        long[][] dp = new long[3][7];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        for (int i = 0; i < dp[0].length; i++) {
            System.out.print(dp[dp.length-1][i] + "\t");
        }
    }
}
